#  二叉搜索树的最近公共祖先： https://leetcode-cn.com/problems/lowest-common-ancestor-of-a-binary-search-tree/

# 通用解法
class TreeNode:
    def __init__(self, x):
        self.val = x
        self.left = None
        self.right = None


class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
            是236号算法题的简单版。 那是一颗普通二叉树。
            这里还使用通用解法试试，不管它是否是 二叉搜索树
        """
        def getCommonParentNode(node, p, q):
            if not node: return None

            left = getCommonParentNode(node.left, p, q)
            right = getCommonParentNode(node.right, p, q)

            if left and right or node == p or node == q:
                return node
            if left:
                return left
            elif right:
                return right
            else:
                return None
        
        return getCommonParentNode(root, p, q)



# 利用二叉搜索树（BST）的性质： 时间复杂度是 O(log n)
class Solution:
    def lowestCommonAncestor(self, root: 'TreeNode', p: 'TreeNode', q: 'TreeNode') -> 'TreeNode':
        """
            利用二叉搜索树（BST）的性质， 其公共根节点必定是 在 p，q两数之间。
            那么我们利用这个性质，从根节点找
            时间复杂度是 O(log n)
        """
        ans = root
        while ans:
            if q.val < ans.val and p.val < ans.val:
                ans = ans.left
            elif q.val > ans.val and p.val > ans.val:
                ans = ans.right
            else:
                # 说明在中间了
                break
        
        return ans



